/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/sliding-window-maximum
   @Language: C++
   @Datetime: 19-03-29 10:18
   */

// Method 1, Time O(nlogk), Space O(k), Time 1811ms
class Solution {
public:
	/**
	 * @param nums: A list of integers.
	 * @param k: An integer
	 * @return: The maximum number inside the window at each moving.
	 * Tip:
	 * each k nums sort it, using multiset
	 */
	vector<int> maxSlidingWindow(vector<int> &nums, int k) {
		// write your code here
		if (nums.size()<1 || nums.size()<k) return {};
		multiset<int,greater<int> > wind(nums.begin(),nums.begin()+k);
		vector<int> v(nums.size()-k+1, *wind.begin());
		for(int i=k; i<nums.size(); ++i){
			wind.erase(wind.find(nums[i-k]));
			wind.insert(nums[i]);
			v[i-k+1]= *wind.begin();
		}
		return v;
	}
};


// Method 2, Time O(n), Space O(k), Time 1006ms
class Solution {
public:
	/**
	 * @param nums: A list of integers.
	 * @param k: An integer
	 * @return: The maximum number inside the window at each moving.
	 * Tip
	 * every num push into window, check it if greater than queue tails
	 * queue front must be greatest num
	 */
	vector<int> maxSlidingWindow(vector<int> &nums, int k) {
		// write your code here
		if (nums.size()<1 || nums.size()<k) return {};
		deque<pair<int,int> > wind={{nums[0],0}};   // num, index
		vector<int> v(nums.size()-k+1,nums[0]);
		for(int i=1; i<nums.size(); ++i){
			for(; wind.size() && nums[i]>wind.back().first; wind.pop_back());
			if (wind.size() && i-wind.front().second==k) wind.pop_front();
			wind.push_back(make_pair(nums[i],i));
			if (i+1>=k) v[i-k+1]=wind.front().first;
		}
		return v;
	}
};
